1. Field of the Invention
The present invention generally relates to semiconductor memory, and more specifically relates to providing an improved content addressable memory (CAM).
2. Background of the Invention
Content addressable memory, also called xe2x80x9cassociative memoryxe2x80x9d, is a type of storage device which includes comparison logic with each bit of storage. A data value is broadcast to all words of storage and compared with the data values in storage. Words that match are flagged in some way. Subsequent operations can then work on flagged words, e.g., read the flagged words out one at a time or write to certain bit positions in all of the flagged words. A CAM can thus operate as a data parallel processor, also referred to as SIMD processor (Single Instruction/Multiple Data). Moreover, content addressable memories are often used in caches and memory management units.
The content addressable memory described in U.S. Pat. No. 5,870,324 has two memory arrays D0xe2x80x2 and D1xe2x80x2 to store all memory locations. The memory array D0xe2x80x2 contains two blocks D00 and D10. The block D00 stores the bit positions 0 to 11 of a first portion of the memory locations, whereas the block D10 stores the bit positions 0 to 11 of a second portion of the memory locations. The memory array D1xe2x80x2 contains blocks D01 and D11, which store the bit positions 12 to 23 of the first and the second portion of the memory locations, respectively. A location with a width of 24 bits is therefore divided into two halves in the described CAM.
The memory arrays D0xe2x80x2 and D1xe2x80x2 are each electrically linked through bit line drivers and write heads S0xe2x80x2 and S with the input lines B0 to B11 and compare lines CD0 to CD1, and with the input lines B12 to B23 and the compare lines CD12 to CD23, respectively. A read/write memory block E0xe2x80x2 belongs to the memory array D0xe2x80x2, whereas a read/write memory block E1xe2x80x2 belongs to the memory array D1xe2x80x2. The read/write memory blocks E0xe2x80x2 and E1xe2x80x2 have both an enable circuit, which allows writing in a read/write cell of one of the blocks E0xe2x80x2 or E1xe2x80x2. Each of the blocks D00, D01, D10 and D11 is linked through corresponding match lines MATCH00, MATCH01, MATCH10 and MATCH11 with an enable circuits. Each location having 12-bit positions of one of the blocks D00, D0, D10 and D11 thereby has a separate match line.
The match lines MATCH00 and MATCH01 , or MATCH10 and MATCH11, are linked logically in an AND-operation in the enable circuits. Only when both of the match lines MATCH00 and MATCH01, or MATCH10 and MATCH11, indicate that the corresponding bit positions of the comparison data on the match line correspond to those bits stored in the blocks of a data word, the corresponding enable circuit gets activated for that location in the blocks in which the agreement was determined. The information of the agreement of the comparison data and a stored data word is then flagged by writing into a corresponding read/write cell of one of the read/write blocks E0xe2x80x2 or E1xe2x80x2. This information can then be read out through output lines Out0 and Out1 which are linked with the read/write blocks E0xe2x80x2 or E1xe2x80x2 through output drivers. The enable circuit, the logical AND-operation of the match lines and the read/write cell of the memory block E0xe2x80x2 is implemented for each memory location of the CAM.
An object of the present invention is to provide an improved content addressable memory which will flag memory locations of which the content only partially matches a given comparison value.
A content addressable memory according to the present invention has at least one memory array having a number of memory locations. Each memory location has a predetermined number of memory cells, whereby each memory cell is able to store 1 bit of information. In the case of the memory locations having 16 memory cells, then each memory location is able to store 16 bits of information. Although 16 memory cells might form one memory location, this does not necessarily mean that all 16 memory cells forming one memory location have to be positioned adjacent to each other. It might rather be advantageous, e.g., for wiring reasons, to place memory cells side by side that belong to different memory locations.
The memory array is divided into at least a first memory block and a second memory block. It is acknowledged that, without departing from the spirit of the invention, the memory array might also be divided into more than two separate memory blocks. The first memory block is formed by a first portion of each of the memory locations and a second memory block is formed by a second portion of each of the memory locations. In other words, one part of the memory cells, e.g., the memory cells representing the lower 8 bits of the memory locations, are grouped to form the first memory block and another part of the memory cells, e.g., the memory cells representing the upper 8 bits of the memory locations, are grouped to form the second memory block.
The content addressable memory according to the present invention also has a first set and a second set of compare lines which are associated to the first and the second memory block, respectively. Compare lines are generally used to apply comparison values-to comparison units, one of which is associated to each memory cell. For example, the compare line carrying the compare signal representing the reference value of bit position 3 is connected to all comparison units associated to memory cells storing the bit position 3 in a memory location. Thus, there are as many logically different compare lines as there are bit positions in one memory location. However, physically there might be a higher number due to wiring constraints.
Furthermore, the content addressable memory includes a first and a second set of match lines, whereas the first set of match lines is associated to the first memory block, and the second set of match lines is associated to the second memory block. A match line generally combines the output of all comparison units belonging to one memory location. However, since, according to the present invention, each memory location is divided into at least two portions, two times as many match lines as there are memory locations are distinguished.
Pre-charge units are provided for charging the match lines before a comparison operation. For performance reason the content-addressable memory according to the present invention is implemented using dynamic logic. Therefore, pre-charging of the match lines is necessary. The pre-charging brings the match line into a high-level state. During the following comparison operation, the match line keeps its high-level state if all bit positions of a memory location correspond to the respective bit positions of the comparison value. In case there is only one mismatch, the level of the match line is pulled down to a low-level state. The pre-charge units may be combined with other units, e.g., with a comparison unit, or may be distributed, e.g., parts connected to the match line, whereas other parts might be connected to the comparison unit. The pre-charge units may even not directly cause the match line to go into the pre-charge-state, as it will be apparent from the detailed description of a preferred embodiment below.
In order to allow that a match of only a subset of all bit positions of a memory location with the respective comparison value generates a match signal, the results of the comparison of the first memory block and the result of the comparison of the second memory block are logically combined. In the above example, in which a 16 bit wide memory location is divided into a lower and an upper 8 bit portion, a partial match of either the lower 8 bits or the upper 8 bits might generate a match signal, depending on how the results of both comparisons are combined. In the case of only the upper 8 bits are required to match, the result of the lower 8 bits may be neglected. This can be implemented by a combination logic being present for each pair of match lines, whereby the combination logic is controlled by select signals indicating which portion of the contents of a memory location must match.
Alternatively, the content addressable memory uses the pre-charge state of the match lines as a logically valid state, which leads advantageously to a reduction in the number of physical conductor lines which have to be provided in the circuit layout.
In a preferred embodiment of the content addressable memory according to the present invention, a first select signal line, a first functional unit, a second select signal line and a second functional unit are provided, whereby the first select signal line is connected to an input terminal of the first functional unit and the second select signal line is connected to an input terminal of the second functional unit. The functional units determine under which circumstances the comparison of one or the other memory block gets neglected. Of course, there is still the possibility that the whole content of a memory location has to match to the reference value. The state in which both comparison results are ignored might be used as a xe2x80x98general resetxe2x80x99 for output registers or latches storing the result of a comparison.
Furthermore, the output of the first functional unit is connected to the pre-charge units associated to the first memory block and, correspondingly, the output of the second functional unit is connected to the pre-charge units associated to the second memory block.
In addition, the functional units are configured to keep the respectively connected pre-charge units in a pre-charged state during the comparison operation when the associated select signal line shows a predetermined level. In other words, when a comparison of one memory block needs to be ignored, then the match line is forced by the functional unit and the pre-charge unit to the stay in the pre-charge state also during the comparison phase. Thus, according to the present invention, the precharge state is under certain conditions considered to be the valid logical state representing a match of all bit positions of the respective memory block. Therefore, if the comparison of a portion of bit positions that has to be ignored behave as if it was a match condition, only a mismatch in a bit position of the other portion could cause an overall mismatch. Hence, the match line pairs may be connected to each other without providing a combination logic for each pair of match lines. Instead, only one functional unit is needed for each memory block, i.e., two functional units for the example above.
In another preferred embodiment, the compare lines are connected to respective pre-charge units associated with the related match line. In addition, each pre-charge unit may have two output lines and may be configured to generate a true-signal and a complement-signal formed from the respective compare line signal when the output signal of the associated functional unit has a first level, and may generate the same signal on both output lines when the output signal of the associated functional unit has a second level.
Each functional unit may have other input terminals connected to a clock signal line. Advantageously, each functional unit may be configured to generate an output signal of a first level causing the respective pre-charge units to stay in a pre-charge state when the respective select signal has a predetermined level, independent from the clock signal level.